package algorithm.array;

/**
 * Leetcode: https://leetcode.com/problems/majority-element/
 * Medium
 *
 * 给一个数组，找到数组中占多数的元素。（占多数是指数量超过一半的数）
 * Created by yzy on 2021-03-03 19:37
 */
public class MajorityElement {


    /**
     * 摩尔投票法。faster than 99.99%
     * 从第一个数开始数，遇到相同的+1，不同的-1。减到0就换一个数。
     * 最后剩下的数一定是占超过一半的数
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int currNum = nums[0];
        int count=1;
        for(int i=1; i<nums.length; i++){
            if(nums[i] == currNum){
                count++;
            }else{
                count--;
            }
            if(count==0){
                currNum = nums[i];
                count=1;
            }
        }
        return currNum;
    }
}
